home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 June: Reference Library / Dev.CD Jun 96 RL / Dev.CD Jun 96 RL.toast / Technical Documentation / develop / develop Issue 24 / develop Issue 24 code / Scriptable Database 1.0a15 / Database / DBRecord.cp < prev    next >
Encoding:
Text File  |  1996-04-25  |  49.9 KB  |  1,528 lines  |  [TEXT/CWIE]

  1. //================================================================================
  2. // Greg Anderson
  3. // db+
  4. //
  5. // Cursor to an database record
  6. // 16 May 1994
  7. // 31 Dec 1994
  8. //
  9. // Every database record is an entry in a balanced binary tree.  The
  10. // exact type of tree used is an AVL tree (named after it inventors,
  11. // G.M. Adelson-Velskii and E.M. Landis), as described in
  12. // _Data Structures & Program Design_, (2nd edition) by R.L. Kruse,
  13. // pp. 344-356.
  14. //================================================================================
  15.  
  16. #include "DBRecord.h"
  17.  
  18. #include "Transaction.h"
  19.  
  20. #include "Exceptions.h"
  21.  
  22. #define INHERITED TAbstractRecord
  23.  
  24. //--------------------------------------------------------------------------------
  25. // TDBRecord::~TDBRecord
  26. //--------------------------------------------------------------------------------
  27. TDBRecord::~TDBRecord()
  28. {
  29. } // TDBRecord::~TDBRecord
  30.  
  31. //--------------------------------------------------------------------------------
  32. // TDBRecord::CompareTreeOrder
  33. //--------------------------------------------------------------------------------
  34. CompareEnumeration TDBRecord::CompareTreeOrder(TTransaction* t, AConst<TDBRecord> secondObject) const
  35. {
  36.     CompareEnumeration theOrder = this->CompareSortKeys(t, secondObject);
  37.     if(theOrder == kObjectKeysEqual)
  38.         theOrder = this->DetermineCompareEnumeration(this->RecordIndex(), secondObject->RecordIndex());
  39.     return theOrder;
  40. } // TDBRecord::CompareTreeOrder
  41.  
  42. //--------------------------------------------------------------------------------
  43. // TDBRecord::FreeOwnedData
  44. //--------------------------------------------------------------------------------
  45. void TDBRecord::FreeOwnedData(TTransaction* t)
  46. {
  47.     //
  48.     // If this entry contains any sub-elements, make them all free
  49.     // (they will in turn free all of their sub-elements)
  50.     //
  51.     if(this->RecordCanHaveElements(t))
  52.     {
  53.         AConst<TDBRecord> elements = this->TopElementRecord(t);
  54.         if(elements.Exists())
  55.             (this->Transaction()->GetDBRecordUpdatePointer(elements))->FreeEntireTree(t);
  56.     }
  57.     
  58.     //
  59.     // If this entry contains any properties, make them all free
  60.     // (they will in turn free all of their referenced data)
  61.     //
  62.     if(this->RecordCanHaveProperties(t))
  63.     {
  64.         AConst<TDBRecord> properties = this->TopPropertyRecord(t);    
  65.         if(properties.Exists())
  66.             (this->Transaction()->GetDBRecordUpdatePointer(properties))->FreeEntireTree(t);
  67.     }
  68.     
  69.     INHERITED::FreeOwnedData(t);
  70. } // TDBRecord::FreeOwnedData
  71.  
  72. //--------------------------------------------------------------------------------
  73. // TDBRecord::FreeThisRecord
  74. //--------------------------------------------------------------------------------
  75. void TDBRecord::FreeThisRecord(TTransaction* t)
  76. {
  77.     //
  78.     // If this record is part of a tree, then remove it
  79.     //
  80.     if(this->RecordIsInATree(t))
  81.         this->RemoveFromTree(t);
  82.         
  83.     INHERITED::FreeThisRecord(t);
  84. } // TDBRecord::FreeThisRecord
  85.  
  86. //--------------------------------------------------------------------------------
  87. // TDBRecord::FreeEntireTree
  88. //
  89. // This is a DANGEROUS routine; it frees this record and all of its siblings!
  90. // Usually, you won't want to call it directly; see
  91. // TDBRecord::FreeThisRecord.
  92. //
  93. // NOTE:  No effort is made to remove any existing references to this tree;
  94. // it is assumed that the caller will do that before deleting the tree.
  95. //--------------------------------------------------------------------------------
  96. void TDBRecord::FreeEntireTree(TTransaction* t)
  97. {
  98.     //
  99.     // We could just use an iterator, but it would be inefficient to
  100.     // call RemoveCurrent on every node when we are just trying to 
  101.     // delete everything anyway.
  102.     //
  103.     AConst<TDBRecord> current = this->FirstItemInSubTree(t);
  104.     while(current.Exists())
  105.     {
  106.         AConst<TDBRecord> next;
  107.         
  108.         //
  109.         // If 'current' has children, then go down
  110.         // to the last child in the tree and do nothing
  111.         // else this iteration 
  112.         //
  113.         if(current->HasLeftSibling(t))
  114.             next = current->FirstItemInSubTree(t);
  115.         else if(current->HasRightSibling(t))
  116.             next = current->LastItemInSubTree(t);
  117.         //
  118.         // If 'current' has no children, then free it
  119.         //
  120.         else
  121.         {
  122.             //
  123.             // The first thing to do is to go up to the
  124.             // parent and remove the link that points to
  125.             // the record we are deleting.  Once the node
  126.             // to be deleted has been snipped from the tree,
  127.             // we delete it.
  128.             //
  129.             next = current->ParentSibling(t);
  130.             if(next.Exists())
  131.             {
  132.                 ChildIdentifier whichChild = next->IdentifyChild(t, current);
  133.                 (this->Transaction()->GetDBRecordUpdatePointer(next))->SetChildLinkOfNewParent(t, AConst<TDBRecord>(nil), whichChild);
  134.             }
  135.             //
  136.             // Set the parent sibling of the current node to 'nil'
  137.             // so that it will not be removed from the tree when
  138.             // we call 'FreeThisRecord' (since we just removed
  139.             // it manually).
  140.             //
  141.             (this->Transaction()->GetDBRecordUpdatePointer(current))->SetParentSibling(t, nil);
  142.             (this->Transaction()->GetDBRecordUpdatePointer(current))->FreeThisRecord(t);
  143.         }
  144.         
  145.         //
  146.         // We're done with the current node (for now... if it had
  147.         // children, we'll come back to it later); go on to the 'next' node.
  148.         //
  149.         current = next;
  150.     }
  151. } // TDBRecord::FreeEntireTree
  152.  
  153. //--------------------------------------------------------------------------------
  154. // TDBRecord::IdentifyChild
  155. //
  156. // Determine how 'testChild' is linked to this record, or return
  157. // 'kNodeIsNotAChild' if it is not.
  158. //--------------------------------------------------------------------------------
  159. ChildIdentifier TDBRecord::IdentifyChild(TTransaction* t, AConst<TDBRecord> testChild) const
  160. {
  161.     Require(testChild.Exists());
  162.     
  163.     ChildIdentifier childID = kNodeIsNotAChild;
  164.     long testChildIndex = testChild->RecordIndex();
  165.  
  166.     //
  167.     // Find a link that points to the testChild
  168.     //
  169.     if(this->LeftSiblingIndex(t) == testChildIndex)
  170.         childID = kNodeIsLeftChild;
  171.     else if(this->RightSiblingIndex(t) == testChildIndex)
  172.         childID = kNodeIsRightChild;
  173.     else if(this->RecordCanHaveElements(t) && (this->TopChildIndex(t) == testChildIndex))
  174.         childID = kNodeIsTopOfElementTree;
  175.     else if(this->RecordCanHaveProperties(t) && (this->TopPropertyIndex(t) == testChildIndex))
  176.         childID = kNodeIsTopOfPropertyTree;
  177.     
  178.     //
  179.     // Make sure that the 'testChild' is marked as being
  180.     // at the top of the tree if it is in a 'top of tree'
  181.     // pointer, and make sure that it is not marked as being
  182.     // at the top of the tree if it is not.
  183.     //
  184.     if((childID == kNodeIsLeftChild) || (childID == kNodeIsRightChild))
  185.         Require(testChild->RecordIsAtTopOfTree(t) == false);
  186.     if((childID == kNodeIsTopOfElementTree) || (childID == kNodeIsTopOfPropertyTree))
  187.         Require(testChild->RecordIsAtTopOfTree(t) == true);
  188.  
  189.     return childID;
  190. } // TDBRecord::IdentifyChild
  191.  
  192. //--------------------------------------------------------------------------------
  193. // TDBRecord::DeepestSubtree
  194. //
  195. // Debugging function only
  196. //--------------------------------------------------------------------------------
  197. long TDBRecord::DeepestSubtree(TTransaction* t) const
  198. {
  199.     long leftDepth = 0;
  200.     AConst<TDBRecord> left = this->LeftSibling(t);
  201.     if(left.Exists())
  202.     {
  203.         leftDepth = 1 + left->DeepestSubtree(t);
  204.     }
  205.     long rightDepth = 0;
  206.     AConst<TDBRecord> right = this->RightSibling(t);
  207.     if(right.Exists())
  208.     {
  209.         rightDepth = 1 + right->DeepestSubtree(t);
  210.     }
  211.     
  212.     return rightDepth > leftDepth ? rightDepth : leftDepth;
  213. } // TDBRecord::DeepestSubtree
  214.  
  215. //--------------------------------------------------------------------------------
  216. // TDBRecord::Verify
  217. //--------------------------------------------------------------------------------
  218. void TDBRecord::Verify(TTransaction* t, Boolean verifyDeep /* = false */) const
  219. {
  220.     if(    (this->RecordIndex() == this->ParentSiblingIndex(t)) ||
  221.         (this->RecordIndex() == this->LeftSiblingIndex(t)) ||
  222.         (this->RecordIndex() == this->RightSiblingIndex(t)) )
  223.         DebugStr("\ppTDBRecord::Verify record points at itself!");
  224.  
  225.     //
  226.     // First check out the parent sibling link
  227.     //
  228.     AConst<TDBRecord> parent = this->LiteralParentSibling(t);
  229.     if(parent.Exists())
  230.     {
  231.         if(parent->IdentifyChild(t, AConst<TDBRecord>(this)) == kNodeIsNotAChild)
  232.             DebugStr("\pTDBRecord::Verify parent doesn't point back");
  233.     }
  234.     
  235.     //
  236.     // Next check left and right siblings
  237.     //
  238.     AConst<TDBRecord> left = this->LeftSibling(t);
  239.     if(left.Exists())
  240.     {
  241.         if(left->LiteralParentSibling(t)->RecordIndex() != this->RecordIndex())
  242.             DebugStr("\pTDBRecord::Verify left sibling doesn't point back");
  243.     }
  244.     AConst<TDBRecord> right = this->RightSibling(t);
  245.     if(right.Exists())
  246.     {
  247.         if(right->LiteralParentSibling(t)->RecordIndex() != this->RecordIndex())
  248.             DebugStr("\pTDBRecord::Verify right sibling doesn't point back");
  249.     }
  250.     
  251.     //
  252.     // In deep verifies, we recursively verify the left and right
  253.     // children, and we also test the tree order of this nodes
  254.     // predecessor and successor, and check out the node's balance factor.
  255.     //
  256.     if(verifyDeep)
  257.     {
  258.         if(left.Exists())
  259.             left->Verify(t, verifyDeep);
  260.         if(right.Exists())
  261.             right->Verify(t, verifyDeep);
  262.         
  263. #if 0
  264.         //
  265.         // Test the ordering of the elements in the tree
  266.         // (note: elements are sometimes temporarily mis-ordered,
  267.         // then are put back into order, hense the #if 0)
  268.         //
  269.         AConst<TDBRecord> predecessor = this->PreviousItemInTree(t);
  270.         if(predecessor.Exists())
  271.         {
  272.             if(this->CompareTreeOrder(t, predecessor) != kSecondObjectComesBefore)
  273.                 DebugStr("\pRecord should go before its predecessor!");
  274.         }
  275.         AConst<TDBRecord> successor = this->NextItemInTree(t);
  276.         if(successor.Exists())
  277.         {
  278.             if(this->CompareTreeOrder(t, successor) != kSecondObjectComesAfter)
  279.                 DebugStr("\pRecord should come after its successor!");
  280.         }
  281. #endif
  282.         
  283.         //
  284.         // Finally, test the recorded balance factor against reality
  285.         //
  286.         long leftDepth = 0;
  287.         if(left.Exists())
  288.             leftDepth = 1 + left->DeepestSubtree(t);
  289.         long rightDepth = 0;
  290.         if(right.Exists())
  291.             rightDepth = 1 + right->DeepestSubtree(t);
  292.         if((rightDepth - leftDepth > 1) || (rightDepth - leftDepth < -1))
  293.             DebugStr("\ppTDBRecord::Verify tree balance factor greater than one");
  294.         else switch(this->BalanceFactor(t))
  295.         {
  296.             case kSubtreesBalanced:
  297.                 if(rightDepth != leftDepth)
  298.                     DebugStr("\pSubtree marked balanced when it isn't");
  299.                 break;
  300.             case kLeftSideHigher:
  301.                 if(rightDepth >= leftDepth)
  302.                     DebugStr("\pSubtree marked left-heavy when it isn't");
  303.                 break;
  304.             case kRightSideHigher:
  305.                 if(rightDepth <= leftDepth)
  306.                     DebugStr("\pSubtree marked right-heavy when it isn't");
  307.                 break;
  308.             default:
  309.                 DebugStr("\pBalance factor set to unknown value");
  310.         }
  311.     }
  312. } // TDBRecord::Verify
  313.  
  314. //--------------------------------------------------------------------------------
  315. // TDBRecord::TopOfTree
  316. //--------------------------------------------------------------------------------
  317. AConst<TDBRecord> TDBRecord::TopOfTree(TTransaction* t) const
  318. {
  319.     AConst<TDBRecord> treeTop = AConst<TDBRecord>(this);
  320.     
  321.     while((treeTop->RecordIsInATree(t)) && (treeTop->RecordIsAtTopOfTree(t) == false))
  322.         treeTop = treeTop->LiteralParentSibling(t);
  323.     
  324.     Require(treeTop.Exists());
  325.     
  326.     return treeTop;
  327. } // TDBRecord::TopOfTree
  328.  
  329. //--------------------------------------------------------------------------------
  330. // TDBRecord::TreeOwner
  331. //--------------------------------------------------------------------------------
  332. AConst<TDBRecord> TDBRecord::TreeOwner(TTransaction* t) const
  333. {
  334.     AConst<TDBRecord> treeTop = this->TopOfTree(t);
  335.     AConst<TDBRecord> owner(nil);
  336.     
  337.     if(treeTop.Exists())
  338.     {
  339.         owner = treeTop->LiteralParentSibling(t);
  340.     }
  341.     
  342.     return owner;
  343. } // TDBRecord::TreeOwner
  344.  
  345. //--------------------------------------------------------------------------------
  346. // TDBRecord::GoUpUntil
  347. //--------------------------------------------------------------------------------
  348. AConst<TDBRecord> TDBRecord::GoUpUntil(TTransaction* t, ChildIdentifier fromDirection) const
  349. {
  350.     AConst<TDBRecord> cameFrom = AConst<TDBRecord>(this);
  351.     AConst<TDBRecord> upTo = cameFrom->ParentSibling(t);
  352.     
  353.     while((upTo.Exists()) && (upTo->IdentifyChild(t, cameFrom) != fromDirection))
  354.     {
  355.         cameFrom = upTo;
  356.         upTo = cameFrom->ParentSibling(t);
  357.     }
  358.     
  359.     return upTo;
  360. } // TDBRecord::GoUpUntil
  361.  
  362. //--------------------------------------------------------------------------------
  363. // TDBRecord::FirstItemInTree
  364. //--------------------------------------------------------------------------------
  365. AConst<TDBRecord> TDBRecord::FirstItemInTree(TTransaction* t) const
  366. {
  367.     AConst<TDBRecord> topOfTree = this->TopOfTree(t);
  368.     AConst<TDBRecord> firstItemInTree = topOfTree->FirstItemInSubTree(t);
  369.     
  370.     return firstItemInTree;
  371. } // TDBRecord::FirstItemInTree
  372.  
  373. //--------------------------------------------------------------------------------
  374. // TDBRecord::LastItemInTree
  375. //--------------------------------------------------------------------------------
  376. AConst<TDBRecord> TDBRecord::LastItemInTree(TTransaction* t) const
  377. {
  378.     AConst<TDBRecord> topOfTree = this->TopOfTree(t);
  379.     AConst<TDBRecord> lastItemInTree = topOfTree->LastItemInSubTree(t);
  380.     
  381.     return lastItemInTree;
  382. } // TDBRecord::LastItemInTree
  383.  
  384. //--------------------------------------------------------------------------------
  385. // TDBRecord::FindItemInTree
  386. //--------------------------------------------------------------------------------
  387. AConst<TDBRecord> TDBRecord::FindItemInTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const
  388. {
  389.     AConst<TDBRecord> topOfTree = this->TopOfTree(t);
  390.     AConst<TDBRecord> foundItem = topOfTree->FindItemInSubTree(t, doCompare);
  391.     
  392.     return foundItem;
  393. } // TDBRecord::FindItemInTree
  394.  
  395. //--------------------------------------------------------------------------------
  396. // TDBRecord::NumberOfChildSiblings
  397. //--------------------------------------------------------------------------------
  398. long TDBRecord::NumberOfChildSiblings(TTransaction* t) const
  399. {
  400.     long childSiblings = 0;
  401.     
  402.     AConst<TDBRecord> left = this->LeftSibling(t);
  403.     AConst<TDBRecord> right = this->RightSibling(t);
  404.  
  405.     if(left.Exists())
  406.         childSiblings += left->NumberOfChildSiblings(t) + 1;
  407.     if(right.Exists())
  408.         childSiblings += right->NumberOfChildSiblings(t) + 1;
  409.     
  410.     return childSiblings;
  411. }
  412.  
  413. //--------------------------------------------------------------------------------
  414. // TDBRecord::FirstItemInSubTree
  415. //--------------------------------------------------------------------------------
  416. AConst<TDBRecord> TDBRecord::FirstItemInSubTree(TTransaction* t) const
  417. {
  418.     AConst<TDBRecord> firstItem = AConst<TDBRecord>(this);
  419.     
  420.     while(firstItem->HasLeftSibling(t))
  421.     {
  422.         firstItem = firstItem->LeftSibling(t);
  423.     }
  424.     return firstItem;
  425. } // TDBRecord::FirstItemInSubTree
  426.  
  427. //--------------------------------------------------------------------------------
  428. // TDBRecord::LastItemInSubTree
  429. //--------------------------------------------------------------------------------
  430. AConst<TDBRecord> TDBRecord::LastItemInSubTree(TTransaction* t) const
  431. {
  432.     AConst<TDBRecord> lastItem = AConst<TDBRecord>(this);
  433.     
  434.     while(lastItem->HasRightSibling(t))
  435.     {
  436.         lastItem = lastItem->RightSibling(t);
  437.     }
  438.     return lastItem;
  439. } // TDBRecord::LastItemInSubTree
  440.  
  441. //--------------------------------------------------------------------------------
  442. // TDBRecord::NextItemInTree
  443. //--------------------------------------------------------------------------------
  444. AConst<TDBRecord> TDBRecord::NextItemInTree(TTransaction* t) const
  445. {
  446.     AConst<TDBRecord> nextItem = this->RightSibling(t);
  447.     
  448.     //
  449.     // If there is a node in our RightSibling slot, then
  450.     // the next node in the tree can be found by going down
  451.     // one step to the right, and then following the left
  452.     // links all the way to the end.
  453.     //
  454.     if(nextItem.Exists())
  455.     {
  456.         nextItem = nextItem->FirstItemInSubTree(t);
  457.     }
  458.     //
  459.     // If there isn't an entry in our RightSibling slot,
  460.     // then the next node in the tree is somewhere above
  461.     // us (or we've come to the end of the tree and should
  462.     // return nil--one or the other).
  463.     //
  464.     else
  465.     {
  466.         nextItem = this->GoUpUntil(t, kNodeIsLeftChild);
  467.     }
  468.     
  469.     return nextItem;    
  470. } // TDBRecord::NextItemInTree
  471.  
  472. //--------------------------------------------------------------------------------
  473. // TDBRecord::PreviousItemInTree
  474. //--------------------------------------------------------------------------------
  475. AConst<TDBRecord> TDBRecord::PreviousItemInTree(TTransaction* t) const
  476. {
  477.     AConst<TDBRecord> previousItem = this->LeftSibling(t);
  478.     
  479.     //
  480.     // If there is a node in our LeftSibling slot, then
  481.     // the previous node in the tree can be found by going down
  482.     // one step to the left, and then following the right
  483.     // links all the way to the end.
  484.     //
  485.     if(previousItem.Exists())
  486.     {
  487.         previousItem = previousItem->LastItemInSubTree(t);
  488.     }
  489.     //
  490.     // If there isn't an entry in our LeftSibling slot,
  491.     // then the previous node in the tree is somewhere above
  492.     // us (or we've come to the beginning of the tree and should
  493.     // return nil--one or the other).
  494.     //
  495.     else
  496.     {
  497.         previousItem = this->GoUpUntil(t, kNodeIsRightChild);
  498.     }
  499.     
  500.     return previousItem;    
  501. } // TDBRecord::PreviousItemInTree
  502.  
  503. //--------------------------------------------------------------------------------
  504. // TDBRecord::FindItemInSubTree
  505. //--------------------------------------------------------------------------------
  506. AConst<TDBRecord> TDBRecord::FindItemInSubTree(TTransaction* t, TAbstractDBComparisonObject* doCompare) const
  507. {
  508.     REQUIREVALIDPOINTER(doCompare);
  509.     
  510.     AConst<TDBRecord> testRecord = AConst<TDBRecord>(this);
  511.     
  512.     while(testRecord.Exists())
  513.     {
  514.         CompareEnumeration theTest = doCompare->TestObject(t, testRecord);
  515.         if(theTest != kObjectKeysEqual)
  516.         {
  517.             //
  518.             // If the second object (the object being examined)
  519.             // comes after the search key, then we'll find the
  520.             // search key somewhere down the left side of the tree
  521.             // (which is where the smaller items are found)
  522.             //
  523.             if(theTest == kSecondObjectComesAfter)
  524.                 testRecord = testRecord->LeftSibling(t);
  525.             else if(theTest == kSecondObjectComesBefore)
  526.                 testRecord = testRecord->RightSibling(t);
  527.         }
  528.         else
  529.             break;
  530.     }
  531.     
  532.     return testRecord;
  533. } // TDBRecord::FindItemInSubTree
  534.  
  535. //--------------------------------------------------------------------------------
  536. // TDBRecord::Insert
  537. //--------------------------------------------------------------------------------
  538. Boolean TDBRecord::Insert(TTransaction* t, AnUpdate<TDBRecord> insertThis)
  539. {
  540.     Boolean treeGrewTaller = false;
  541.  
  542.     Require(insertThis->RecordIsInATree(t) == false);
  543.     Require((insertThis->HasRightSibling(t) == false) && (insertThis->HasLeftSibling(t) == false));
  544.  
  545.     //
  546.     // Case 1:  Insert to the right
  547.     //
  548.     if(this->CompareTreeOrder(t, insertThis) == kSecondObjectComesAfter)
  549.     {
  550.         //
  551.         // We want to insert the node to the right; if there's nothing
  552.         // to the right, then we can just fill in the empty slot
  553.         //
  554.         if(this->HasRightSibling(t) == false)
  555.         {
  556.             ASSERT(this->BalanceFactor(t) != kRightSideHigher);
  557.             
  558.             insertThis->SetRecordIsAtTopOfTree(t, false);
  559.             insertThis->SetParentSibling(t, this);
  560.             insertThis->SetBalanceFactor(t, kSubtreesBalanced);
  561.             this->SetRightSibling(t, insertThis);
  562.             
  563.             //
  564.             // The right subtree was empty; now it has one node.
  565.             //
  566.             treeGrewTaller = true;
  567.         }
  568.         //
  569.         // If there's already something to the right, then
  570.         // we need to make a recursive call to insert
  571.         //
  572.         else
  573.         {
  574.             AConst<TDBRecord> rightChild = this->RightSibling(t);
  575.             treeGrewTaller = (this->Transaction()->GetDBRecordUpdatePointer(rightChild))->Insert(t, insertThis);
  576.         }
  577.  
  578.         //
  579.         // At this point we know that we inserted a node
  580.         // somewhere on the right branch.  'treeGrewTaller'
  581.         // is true if the right subtree grew taller, false
  582.         // if it stayed the same height.  The node was balanced
  583.         // before the insert, so if the right subtree did not
  584.         // change in height, then we know that this node is
  585.         // still balanced.
  586.         //
  587.         if(treeGrewTaller)
  588.         {
  589.             switch(this->BalanceFactor(t))
  590.             {
  591.                 //
  592.                 // If this node was balanced and the right side just
  593.                 // grew taller, then mark this node as being right-heavy
  594.                 // and note that this subtree has grown taller.
  595.                 //
  596.                 case kSubtreesBalanced:
  597.                 {
  598.                     this->SetBalanceFactor(t, kRightSideHigher);
  599.                     treeGrewTaller = true;
  600.                     break;
  601.                 }
  602.                 //
  603.                 // If the left side of this tree used to be one
  604.                 // node taller than the right, and the right subtree
  605.                 // just grew taller by one, then mark this node as
  606.                 // being balanced and note that this tree did not
  607.                 // grow any taller.
  608.                 //
  609.                 case kLeftSideHigher:
  610.                 {
  611.                     this->SetBalanceFactor(t, kSubtreesBalanced);
  612.                     treeGrewTaller = false;
  613.                     break;
  614.                 }
  615.                 
  616.                 //
  617.                 // If the right subtree was already taller than
  618.                 // the left subtree, and the right side grew again,
  619.                 // then we need to do a right-side balance. 
  620.                 //
  621.                 case kRightSideHigher:
  622.                 {
  623.                     this->RightBalance(t);
  624.                     treeGrewTaller = false;
  625.                     break;
  626.                 }
  627.             }
  628.         }
  629. #if SLOWDEBUG
  630.         //
  631.         // The tree above us may need to be balanced,
  632.         // but at this point this subtree should verify.
  633.         //
  634.         this->Verify(t, true);
  635. #endif
  636.     }
  637.     //
  638.     // Case 2:  Insert to the left
  639.     //
  640.     else
  641.     {
  642.         if(this->HasLeftSibling(t) == false)
  643.         {
  644.             ASSERT(this->BalanceFactor(t) != kLeftSideHigher);
  645.             insertThis->SetRecordIsAtTopOfTree(t, false);
  646.             insertThis->SetParentSibling(t, this);
  647.             insertThis->SetBalanceFactor(t, kSubtreesBalanced);
  648.             this->SetLeftSibling(t, insertThis);
  649.             treeGrewTaller = true;
  650.         }
  651.         else
  652.         {
  653.             AConst<TDBRecord> leftChild = this->LeftSibling(t);
  654.             treeGrewTaller = (this->Transaction()->GetDBRecordUpdatePointer(leftChild))->Insert(t, insertThis);
  655.         }
  656.         if(treeGrewTaller)
  657.         {
  658.             switch(this->BalanceFactor(t))
  659.             {
  660.                 case kSubtreesBalanced:
  661.                 {
  662.                     this->SetBalanceFactor(t, kLeftSideHigher);
  663.                     treeGrewTaller = true;
  664.                     break;
  665.                 }
  666.                 case kRightSideHigher:
  667.                 {
  668.                     this->SetBalanceFactor(t, kSubtreesBalanced);
  669.                     treeGrewTaller = false;
  670.                     break;
  671.                 }
  672.                 case kLeftSideHigher:
  673.                 {
  674.                     this->LeftBalance(t);
  675.                     treeGrewTaller = false;
  676.                     break;
  677.                 }
  678.             }
  679.         }
  680. #ifdef SLOWDEBUG
  681.         this->Verify(t, true);
  682. #endif
  683.     }
  684.     
  685.     return treeGrewTaller;
  686. } // TDBRecord::Insert
  687.  
  688.  
  689. //--------------------------------------------------------------------------------
  690. // TDBRecord::RemoveFromTree
  691. //--------------------------------------------------------------------------------
  692. void TDBRecord::RemoveFromTree(TTransaction* t)
  693. {
  694.     //
  695.     // Don't do anything unless we're part of a tree
  696.     //
  697.     if(this->RecordIsInATree(t))
  698.     {
  699. #if 0
  700.         //
  701.         // Before we do anything, verify that everything in
  702.         // this tree is valid
  703.         //
  704.         // Note:  Sometimes this will cause assertions to
  705.         // fire; for example, if the item is being removed 
  706.         // from ResortThisRecord, then verify will report
  707.         // that the tree is not sorted correctly
  708.         //
  709.         AConst<TDBRecord> treeTop = this->TopOfTree(t);
  710.         treeTop->Verify(t, true);
  711. #endif
  712.     
  713.         //
  714.         // If this node has two children, then we need to swap its
  715.         // position in the tree with its immediate predecessor, found
  716.         // by stepping down to the left once and then walking as far to
  717.         // the right as possible.  This changes the order of the tree
  718.         // temporarily (this item and its previous item are now out
  719.         // of order), but once this item is removed all items remaining
  720.         // in the tree will be in the correct order.
  721.         //
  722.         if((this->HasRightSibling(t) == true) && (this->HasLeftSibling(t) == true))
  723.         {
  724.             AConst<TDBRecord> swapNode = this->PreviousItemInTree(t);
  725.             this->SwapTreePositions(t, this->Transaction()->GetDBRecordUpdatePointer(swapNode));
  726. #ifdef SLOWDEBUG
  727.             this->TopOfTree(t)->Verify(t, true);
  728. #endif
  729.         }
  730.  
  731.         //
  732.         // Remember our parent node before we put our child into the
  733.         // slot we used to occupy (since we might not have a child, and
  734.         // we don't want to loose our reference to the parent)
  735.         //
  736.         AConst<TDBRecord> balancePoint = this->ParentSibling(t);
  737.         
  738.         //
  739.         // Now that we have zero or one children, move up our
  740.         // child list to the slot that we are vacating.
  741.         // If we don't have any children, then don't bother
  742.         // to do the move.
  743.         //
  744.         AConst<TDBRecord> moveUp(nil);
  745.         if(this->HasLeftSibling(t) == true)
  746.         {
  747.             moveUp = this->LeftSibling(t);
  748.             this->SetLeftSibling(t, nil);
  749.         }
  750.         else if(this->HasRightSibling(t) == true)
  751.         {
  752.             moveUp = this->RightSibling(t);
  753.             this->SetRightSibling(t, nil);
  754.         }
  755.         
  756.         //
  757.         // Make the parent of 'moveUp' be the parent of
  758.         // this node; at this point, 'this' shouldn't have
  759.         // any references inside this tree--it has been
  760.         // completely removed.  All that remains to be done
  761.         // is to rebalance the AVL tree.
  762.         //
  763.         // n.b. If 'moveUp' is nil, then SetParentsLinkTothisNodeTo
  764.         // will nil out the parents link to this node
  765.         //
  766.         ChildIdentifier    deletedFromSide = this->SetParentsLinkToThisNodeTo(t, moveUp);
  767. #ifdef SLOWDEBUG
  768.         if(moveUp.Exists())
  769.         {
  770.             moveUp->Verify(t, true);
  771.         }
  772. #endif
  773.         
  774.         //
  775.         // 'deletedFromSide' will almost always be 'left child' or
  776.         // 'right child'.  The only exception is if we just removed
  777.         // the root of the tree, which is only possible in a two-node
  778.         // tree (otherwise the root would have been swapped with
  779.         // some leaf node, and we would be removing a leaf, not the root).
  780.         //
  781.         if((deletedFromSide == kNodeIsLeftChild) || (deletedFromSide == kNodeIsRightChild))
  782.         {
  783.             //
  784.             // Keep fixing up the balancing of the tree until we
  785.             // get a point where the tree is longer on the other
  786.             // branch (the one we didn't delete from); at that
  787.             // point we can mark the tree as balanced and stop
  788.             // adjusting it.
  789.             //
  790.             Boolean treeBecameShorter = true;
  791.             while((balancePoint.Exists()) && (treeBecameShorter == true))
  792.             {
  793. #ifdef SLOWDEBUG
  794.                 //
  795.                 // At this point in the execution of Remove, we know that
  796.                 // the balance point is unbalanced, but its children should
  797.                 // be okay
  798.                 //
  799.                 AConst<TDBRecord> verifyLeft = balancePoint->LeftSibling(t);
  800.                 if(verifyLeft.Exists())
  801.                     verifyLeft->Verify(t, true);
  802.                 AConst<TDBRecord> verifyRight = balancePoint->RightSibling(t);
  803.                 if(verifyRight.Exists())
  804.                     verifyRight->Verify(t, true);
  805. #endif
  806.  
  807.                 //
  808.                 // We must record which node we're planning on going to
  809.                 // next right away, because otherwise a tree rotation
  810.                 // could push 'balancePoint' down; if that happens, we
  811.                 // want to go up to the balance point's former parent,
  812.                 // not its new parent.
  813.                 //
  814.                 AConst<TDBRecord> nextBalancePoint = balancePoint->ParentSibling(t);
  815.                 ChildIdentifier nextDeletedFromSide = kNodeIsNotAChild;
  816.                 if(nextBalancePoint.Exists())
  817.                     nextDeletedFromSide = nextBalancePoint->IdentifyChild(t, balancePoint);
  818.                 
  819.                 //
  820.                 // Set 'testFactor' to the side we _didn't_ delete
  821.                 // from (if the balance point was exactly balanced,
  822.                 // we'll set its balance factor to this value) 
  823.                 //
  824.                 long testFactor = ((deletedFromSide == kNodeIsLeftChild) ? kRightSideHigher : kLeftSideHigher);
  825.         
  826.                 //
  827.                 // Case 1:  Removing a node from a balanced subtree.
  828.                 //            Mark the tree unbalanced, and we're done
  829.                 //
  830.                 if(balancePoint->BalanceFactor(t) == kSubtreesBalanced)
  831.                 {
  832.                     (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, testFactor);
  833.                     treeBecameShorter = false;
  834.                 }
  835.                 //
  836.                 // Case 2:    Removing a node from the longer side of
  837.                 //            an unbalanced subtree.  Mark the tree balanced,
  838.                 //            but keep going.
  839.                 //
  840.                 else if(balancePoint->BalanceFactor(t) != testFactor)
  841.                 {
  842.                     (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kSubtreesBalanced);
  843.                     treeBecameShorter = true;
  844.                 }
  845.                 //
  846.                 // Case 3:    Removing a node from the shorter side of an
  847.                 //            unbalanced subtree.  Rotations are necessary
  848.                 //            to bring the tree back into alignment
  849.                 //
  850.                 else
  851.                 {
  852.                     AConst<TDBRecord> tallerSubtree = (deletedFromSide == kNodeIsLeftChild) ? balancePoint->RightSibling(t) : balancePoint->LeftSibling(t);
  853.                     Require(tallerSubtree.Exists());
  854.                     
  855.                     //
  856.                     // Case 3a:    Taller subtree is balanced
  857.                     //
  858.                     if(tallerSubtree->BalanceFactor(t) == kSubtreesBalanced)
  859.                     {
  860.                         if(deletedFromSide == kNodeIsLeftChild)
  861.                         {
  862.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kRightSideHigher);
  863.                             (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kLeftSideHigher);
  864.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateLeft(t);
  865.                         }
  866.                         else
  867.                         {
  868.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kLeftSideHigher);
  869.                             (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kRightSideHigher);
  870.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateRight(t);
  871.                         }
  872.                         treeBecameShorter = false;
  873.                     }
  874.                     //
  875.                     // Case 3b:    Taller subtree has the same balance
  876.                     //            factor as the balance point
  877.                     //
  878.                     else if(tallerSubtree->BalanceFactor(t) == balancePoint->BalanceFactor(t))
  879.                     {
  880.                         (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->SetBalanceFactor(t, kSubtreesBalanced);
  881.                         (this->Transaction()->GetDBRecordUpdatePointer(tallerSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
  882.                         if(deletedFromSide == kNodeIsLeftChild)
  883.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateLeft(t);
  884.                         else
  885.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->RotateRight(t);
  886.                         treeBecameShorter = true;
  887.                     }
  888.                     //
  889.                     // Case 3c:    Taller subtree has a different balance
  890.                     //            factor than the balance point
  891.                     //
  892.                     else
  893.                     {
  894.                         if(deletedFromSide == kNodeIsLeftChild)
  895.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->DoubleRotateRightSide(t);
  896.                         else
  897.                             (this->Transaction()->GetDBRecordUpdatePointer(balancePoint))->DoubleRotateLeftSide(t);
  898.                         treeBecameShorter = true;
  899.                     }
  900.                 }
  901.  
  902. #ifdef SLOWDEBUG
  903.                 //
  904.                 // The balance point should now verify; if the balance
  905.                 // point was moved down, though, then its parent should
  906.                 // also be balanced.
  907.                 //
  908.                 AConst<TDBRecord> balancePointsNewParent = balancePoint->ParentSibling(t);
  909.                 if((balancePointsNewParent.Exists() == false) || (nextBalancePoint.Exists() == false) || (balancePointsNewParent->RecordIndex() == nextBalancePoint->RecordIndex()))
  910.                     balancePoint->Verify(t, true);
  911.                 else
  912.                     balancePointsNewParent->Verify(t, true);
  913. #endif
  914.                 
  915.                 //
  916.                 // Go up to the next node of the tree.  Stop if we
  917.                 // hit the top, or if treeBecameShorter is set to false
  918.                 //
  919.                 balancePoint = nextBalancePoint;
  920.                 deletedFromSide = nextDeletedFromSide;
  921.             }
  922.         }
  923.                 
  924.         //
  925.         // Finally, nil out our parent-sibling link, since we're
  926.         // not part of any tree any longer.  Make sure that we
  927.         // really don't have any left or right child references,
  928.         // and set the bits that indicate that this node is at
  929.         // the top of a tree, and it's subtrees are balanced (which
  930.         // is what an unattached childless node should look like)
  931.         //
  932.         this->SetParentSibling(t, nil);
  933.         if((this->HasRightSibling(t) == true) || (this->HasLeftSibling(t) == true))
  934.             DebugStr("\pOh oh, child sibling links still exist in TDBRecord::RemoveFromTree");
  935.         this->SetRecordIsAtTopOfTree(t, true);
  936.         this->SetBalanceFactor(t, kSubtreesBalanced);
  937.     }
  938. } // TDBRecord::RemoveFromTree
  939.  
  940. //--------------------------------------------------------------------------------
  941. // TDBRecord::ResortThisRecord
  942. //
  943. // The method "ResortThisRecord" should be called whenever the sort key
  944. // for this record changes; doing that removes and re-inserts this record
  945. // in the tree it is currently contained in.
  946. //--------------------------------------------------------------------------------
  947. void TDBRecord::ResortThisRecord(TTransaction* t)
  948. {
  949.     //
  950.     // Hang onto a reference to some other element in
  951.     // the same tree that we're in
  952.     //
  953.     AConst<TDBRecord> someOtherRecord = this->ParentSibling(t);
  954.     if(someOtherRecord.Exists() == false)
  955.         someOtherRecord = this->LeftSibling(t);
  956.     if(someOtherRecord.Exists() == false)
  957.         someOtherRecord = this->RightSibling(t);
  958.     
  959.     //
  960.     // If this is the only record in the tree, then we
  961.     // don't need to resort.
  962.     //
  963.     // Note:  It might be worthwhile to look at the
  964.     // previous and next items in the tree, and only
  965.     // do a resort if this item really does need to
  966.     // move away from its current location.
  967.     //
  968.     if(someOtherRecord.Exists())
  969.     {
  970.         //
  971.         // Remove this entry from the tree, then find the new top-of-tree record
  972.         //
  973.         this->RemoveFromTree(t);
  974.         AConst<TDBRecord> topOfTree = someOtherRecord->TopOfTree(t);
  975. #ifdef SLOWDEBUG
  976.         this->Verify(t);
  977.         topOfTree->Verify(t, true);
  978. #endif
  979.         
  980.         //
  981.         // Reinsert this element back into the tree.
  982.         //
  983.         (this->Transaction()->GetDBRecordUpdatePointer(topOfTree))->Insert(t, this);
  984. #ifdef SLOWDEBUG
  985.         this->Verify(t);
  986.         this->TopOfTree(t)->Verify(t, true);
  987. #endif
  988.     }
  989. } // TDBRecord::ResortThisRecord
  990.  
  991. //--------------------------------------------------------------------------------
  992. // TDBRecord::RightBalance
  993. //
  994. // Assumptions:  A node was just inserted on the right side of this tree, and
  995. // it made the subtree grow taller.  There was already at least one node on
  996. // the right side before the insertion.
  997. //--------------------------------------------------------------------------------
  998. void TDBRecord::RightBalance(TTransaction* t)
  999. {
  1000.     AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
  1001.     Require(rootOfRightSubtree.Exists());
  1002.     
  1003.     switch(rootOfRightSubtree->BalanceFactor(t))
  1004.     {
  1005.         case kRightSideHigher:
  1006.         {
  1007.             //
  1008.             // Do a left rotation
  1009.             //
  1010.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
  1011.             this->SetBalanceFactor(t, kSubtreesBalanced);
  1012.             this->RotateLeft(t);
  1013.             break;
  1014.         }
  1015.  
  1016.         case kLeftSideHigher:
  1017.         {
  1018.             this->DoubleRotateRightSide(t);
  1019.             break;
  1020.         }
  1021.         
  1022.         case kSubtreesBalanced:
  1023.         {
  1024.             //
  1025.             // This should never happen
  1026.             //
  1027.             Require(false);
  1028.             this->Verify(t, true);
  1029.             break;
  1030.         }
  1031.     }
  1032. } // TDBRecord::RightBalance
  1033.  
  1034. //--------------------------------------------------------------------------------
  1035. // TDBRecord::LeftBalance
  1036. //
  1037. // Assumptions:  A node was just inserted on the left side of this tree, and
  1038. // it made the subtree grow taller.  There was already at least one node on
  1039. // the left side before the insertion.
  1040. //--------------------------------------------------------------------------------
  1041. void TDBRecord::LeftBalance(TTransaction* t)
  1042. {
  1043.     AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
  1044.     
  1045.     switch(rootOfLeftSubtree->BalanceFactor(t))
  1046.     {
  1047.         case kLeftSideHigher:
  1048.         {
  1049.             //
  1050.             // Do a right rotation
  1051.             //
  1052.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
  1053.             this->SetBalanceFactor(t, kSubtreesBalanced);
  1054.             this->RotateRight(t);
  1055.             break;
  1056.         }
  1057.  
  1058.         case kRightSideHigher:
  1059.         {
  1060.             this->DoubleRotateLeftSide(t);
  1061.             break;
  1062.         }
  1063.         
  1064.         case kSubtreesBalanced:
  1065.         {
  1066.             //
  1067.             // This should never happen
  1068.             //
  1069.             Require(false);
  1070.             this->Verify(t, true);
  1071.             break;
  1072.         }
  1073.     }
  1074. } // TDBRecord::LeftBalance
  1075.  
  1076. //--------------------------------------------------------------------------------
  1077. // TDBRecord::RotateLeft
  1078. //--------------------------------------------------------------------------------
  1079. void TDBRecord::RotateLeft(TTransaction* t)
  1080. {
  1081.     AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
  1082.     if(rootOfRightSubtree.Exists())
  1083.     {
  1084.         AConst<TDBRecord> leftChildOfRightSubtree = rootOfRightSubtree->LeftSibling(t);
  1085.         
  1086.         this->SetRightSibling(t, leftChildOfRightSubtree);
  1087.         if(leftChildOfRightSubtree.Exists())
  1088.         {
  1089.             (this->Transaction()->GetDBRecordUpdatePointer(leftChildOfRightSubtree))->SetParentSibling(t, this);
  1090.         }
  1091.         this->SetParentsLinkToThisNodeTo(t, rootOfRightSubtree);
  1092.         (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetLeftSibling(t, this);
  1093.         this->SetParentSibling(t, rootOfRightSubtree);
  1094.     }
  1095. } // TDBRecord::RotateLeft
  1096.  
  1097. //--------------------------------------------------------------------------------
  1098. // TDBRecord::RotateRight
  1099. //--------------------------------------------------------------------------------
  1100. void TDBRecord::RotateRight(TTransaction* t)
  1101. {
  1102.     AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
  1103.     if(rootOfLeftSubtree.Exists())
  1104.     {
  1105.         AConst<TDBRecord> rightChildOfRightSubtree = rootOfLeftSubtree->RightSibling(t);
  1106.     
  1107.         this->SetLeftSibling(t, rightChildOfRightSubtree);
  1108.         if(rightChildOfRightSubtree.Exists())
  1109.         {
  1110.             (this->Transaction()->GetDBRecordUpdatePointer(rightChildOfRightSubtree))->SetParentSibling(t, this);
  1111.         }
  1112.         this->SetParentsLinkToThisNodeTo(t, rootOfLeftSubtree);
  1113.         (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetRightSibling(t, this);
  1114.         this->SetParentSibling(t, rootOfLeftSubtree);
  1115.     }
  1116. } // TDBRecord::RotateLeft
  1117.  
  1118. //--------------------------------------------------------------------------------
  1119. // TDBRecord::DoubleRotateRightSide
  1120. //--------------------------------------------------------------------------------
  1121. void TDBRecord::DoubleRotateRightSide(TTransaction* t)
  1122. {
  1123.     AConst<TDBRecord> rootOfRightSubtree = this->RightSibling(t);
  1124.     Require(rootOfRightSubtree.Exists());
  1125.     AConst<TDBRecord> leftSiblingOfRootOfRight = rootOfRightSubtree->LeftSibling(t);
  1126.     Require(leftSiblingOfRootOfRight.Exists());
  1127.     
  1128.     switch(leftSiblingOfRootOfRight->BalanceFactor(t))
  1129.     {
  1130.         case kSubtreesBalanced:
  1131.         {
  1132.             this->SetBalanceFactor(t, kSubtreesBalanced);
  1133.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
  1134.             break;
  1135.         }
  1136.         
  1137.         case kLeftSideHigher:
  1138.         {
  1139.             this->SetBalanceFactor(t, kSubtreesBalanced);
  1140.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kRightSideHigher);
  1141.             break;
  1142.         }
  1143.         
  1144.         case kRightSideHigher:
  1145.         {
  1146.             this->SetBalanceFactor(t, kLeftSideHigher);
  1147.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
  1148.             break;
  1149.         }
  1150.     }
  1151.     (this->Transaction()->GetDBRecordUpdatePointer(leftSiblingOfRootOfRight))->SetBalanceFactor(t, kSubtreesBalanced);
  1152.     (this->Transaction()->GetDBRecordUpdatePointer(rootOfRightSubtree))->RotateRight(t);
  1153.     this->RotateLeft(t);
  1154. } // TDBRecord::DoubleRotateRightSide
  1155.  
  1156. //--------------------------------------------------------------------------------
  1157. // TDBRecord::DoubleRotateLeftSide
  1158. //--------------------------------------------------------------------------------
  1159. void TDBRecord::DoubleRotateLeftSide(TTransaction* t)
  1160. {
  1161.     AConst<TDBRecord> rootOfLeftSubtree = this->LeftSibling(t);
  1162.     Require(rootOfLeftSubtree.Exists());
  1163.     AConst<TDBRecord> rightSiblingOfRootOfLeft = rootOfLeftSubtree->RightSibling(t);
  1164.     Require(rightSiblingOfRootOfLeft.Exists());
  1165.     
  1166.     switch(rightSiblingOfRootOfLeft->BalanceFactor(t))
  1167.     {
  1168.         case kSubtreesBalanced:
  1169.         {
  1170.             this->SetBalanceFactor(t, kSubtreesBalanced);
  1171.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
  1172.             break;
  1173.         }
  1174.         
  1175.         case kRightSideHigher:
  1176.         {
  1177.             this->SetBalanceFactor(t, kSubtreesBalanced);
  1178.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kLeftSideHigher);
  1179.             break;
  1180.         }
  1181.         
  1182.         case kLeftSideHigher:
  1183.         {
  1184.             this->SetBalanceFactor(t, kRightSideHigher);
  1185.             (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->SetBalanceFactor(t, kSubtreesBalanced);
  1186.             break;
  1187.         }
  1188.     }
  1189.     (this->Transaction()->GetDBRecordUpdatePointer(rightSiblingOfRootOfLeft))->SetBalanceFactor(t, kSubtreesBalanced);
  1190.  
  1191.     (this->Transaction()->GetDBRecordUpdatePointer(rootOfLeftSubtree))->RotateLeft(t);
  1192.     this->RotateRight(t);
  1193. } // TDBRecord::DoubleRotateLeftSide
  1194.  
  1195. //--------------------------------------------------------------------------------
  1196. // TDBRecord::InitializeNewRecord
  1197. //--------------------------------------------------------------------------------
  1198. void TDBRecord::InitializeNewRecord(TTransaction* t)
  1199. {
  1200.     Require(this->ThisRecordIsFree(t));
  1201.  
  1202.     this->SetParentSiblingIndex(t, kNilIndex);
  1203.     this->SetLeftSiblingIndex(t, kNilIndex);
  1204.     this->SetRightSiblingIndex(t, kNilIndex);
  1205. } // TDBRecord::InitializeNewRecord
  1206.  
  1207. //--------------------------------------------------------------------------------
  1208. // TDBRecord::PropertyValueChanged
  1209. //
  1210. // Whenever a property changes value, it informs the record that owns it by
  1211. // calling this method.
  1212. //--------------------------------------------------------------------------------
  1213. void TDBRecord::PropertyValueChanged(TTransaction*, AConst<TDBProperty> /*propertyThatChanged*/)
  1214. {
  1215. } // TDBRecord::PropertyValueChanged
  1216.  
  1217. //--------------------------------------------------------------------------------
  1218. // TDBRecord::RecordCanHaveElements
  1219. //
  1220. // This method must return 'true' if the record can contain elements.
  1221. //--------------------------------------------------------------------------------
  1222. Boolean TDBRecord::RecordCanHaveElements(TTransaction*) const
  1223. {
  1224.     return false;
  1225. } // TDBRecord::RecordCanHaveElements
  1226.  
  1227. //--------------------------------------------------------------------------------
  1228. // TDBRecord::RecordCanHaveProperties
  1229. //
  1230. // This method must return 'true' if the record can contain properties.
  1231. //--------------------------------------------------------------------------------
  1232. Boolean TDBRecord::RecordCanHaveProperties(TTransaction*) const
  1233. {
  1234.     return false;
  1235. } // TDBRecord::RecordCanHaveProperties
  1236.  
  1237. //--------------------------------------------------------------------------------
  1238. // TDBRecord::RequireRecordCanHaveElements
  1239. //
  1240. // This method will fail if the record cannot contain elements, or do nothing
  1241. // if it can.
  1242. //--------------------------------------------------------------------------------
  1243. void TDBRecord::RequireRecordCanHaveElements(TTransaction* t) const
  1244. {
  1245.     if(this->RecordCanHaveElements(t) == false)
  1246.          FailErr(eWrongDataType);
  1247. } // TDBRecord::RequireRecordCanHaveElements
  1248.  
  1249. //--------------------------------------------------------------------------------
  1250. // TDBRecord::RequireRecordCanHaveProperties
  1251. //
  1252. // This method will fail if the record cannot contain properties, or do nothing
  1253. // if it can.
  1254. //--------------------------------------------------------------------------------
  1255. void TDBRecord::RequireRecordCanHaveProperties(TTransaction* t) const
  1256. {
  1257.     if(this->RecordCanHaveProperties(t) == false)
  1258.          FailErr(eWrongDataType);
  1259. } // TDBRecord::RequireRecordCanHaveProperties
  1260.     
  1261. //--------------------------------------------------------------------------------
  1262. // TDBRecord::SetChildLinkOfNewParent
  1263. //--------------------------------------------------------------------------------
  1264. void TDBRecord::SetChildLinkOfNewParent(TTransaction* t, AConst<TDBRecord> newChild, ChildIdentifier whichChild)
  1265. {
  1266.     Boolean isAtTop = false;
  1267.     
  1268.     switch(whichChild)
  1269.     {
  1270.         case kNodeIsLeftChild:
  1271.             this->SetLeftSibling(t, newChild);
  1272.             break;
  1273.         
  1274.         case kNodeIsRightChild:
  1275.             this->SetRightSibling(t, newChild);
  1276.             break;
  1277.         
  1278.         case kNodeIsTopOfElementTree:
  1279.             isAtTop = true;
  1280.             this->SetElements(t, newChild);
  1281.             break;
  1282.         
  1283.         case kNodeIsTopOfPropertyTree:
  1284.             isAtTop = true;
  1285.             this->SetProperties(t, newChild);
  1286.             break;
  1287.         
  1288.         default:
  1289.             Throw(eLinksCorrupt);
  1290.     }
  1291.     
  1292.     //
  1293.     // It is possible that someone may want to set the child
  1294.     // link of the new parent to 'nil', in which case we won't
  1295.     // need to point the new child back to its new parent.
  1296.     //
  1297.     if(newChild.Exists())
  1298.     {
  1299.         AnUpdate<TDBRecord> newChildUpdate = this->Transaction()->GetDBRecordUpdatePointer(newChild);
  1300.         newChildUpdate->SetRecordIsAtTopOfTree(t, isAtTop);
  1301.         newChildUpdate->SetParentSibling(t, this);
  1302.     }
  1303. } // TDBRecord::SetChildLinkOfNewParent
  1304.  
  1305. //--------------------------------------------------------------------------------
  1306. // TDBRecord::SetParentsLinkToThisNodeTo
  1307. //
  1308. // This routine is called when 'newChild' is being rotated into the slot that
  1309. // this record formerly occupied.  It is the responsibility of this routine to
  1310. // insure that whichever node previously pointed to this record will
  1311. // thereafter always point to 'newChild' instead.
  1312. //--------------------------------------------------------------------------------
  1313. ChildIdentifier TDBRecord::SetParentsLinkToThisNodeTo(TTransaction* t, AConst<TDBRecord> newChild)
  1314. {
  1315.     AConst<TDBRecord> parentSibling = this->LiteralParentSibling(t);
  1316.     ChildIdentifier whichChild = kNodeIsNotAChild;
  1317.     
  1318.     if(parentSibling.Exists())
  1319.     {
  1320.         whichChild = parentSibling->IdentifyChild(t, this);
  1321.         (this->Transaction()->GetDBRecordUpdatePointer(parentSibling))->SetChildLinkOfNewParent(t, newChild, whichChild);
  1322.         this->SetParentSibling(t, nil);
  1323.         this->SetRecordIsAtTopOfTree(t, false);
  1324.     }
  1325.     
  1326.     return whichChild;
  1327. } // TDBRecord::SetParentsLinkToThisNodeTo
  1328.  
  1329. //--------------------------------------------------------------------------------
  1330. // TDBRecord::SwapTreePositions
  1331. //--------------------------------------------------------------------------------
  1332. void TDBRecord::SwapTreePositions(TTransaction* t, AnUpdate<TDBRecord> swapWith)
  1333. {
  1334.     //
  1335.     // The first step is to look up all of the adjacent
  1336.     // links for both nodes before changing anything
  1337.     //
  1338.     AConst<TDBRecord> thisLeftSibling = this->LeftSibling(t);
  1339.     AConst<TDBRecord> thisRightSibling = this->RightSibling(t);
  1340.     AConst<TDBRecord> thisParent = this->LiteralParentSibling(t);
  1341.     long thisBalanceFactor = this->BalanceFactor(t);
  1342.     AConst<TDBRecord> othersLeftSibling = swapWith->LeftSibling(t);
  1343.     AConst<TDBRecord> othersRightSibling = swapWith->RightSibling(t);
  1344.     AConst<TDBRecord> othersParent = swapWith->LiteralParentSibling(t);
  1345.     long otherBalanceFactor = swapWith->BalanceFactor(t);
  1346.     ChildIdentifier thisLinkage;
  1347.     ChildIdentifier othersLinkage;
  1348.     OSErr err = noErr;
  1349.     
  1350.     //
  1351.     // We really expect that this routine will be called on two
  1352.     // records that are both part of the same tree, but this is
  1353.     // not required; in fact, one of the records may not even
  1354.     // be in a tree.  The one thing that would be really really
  1355.     // bad would be to swap an element with a property; we should
  1356.     // test for this, but we currently do not.
  1357.     //
  1358.     // At any rate, it is very important to remember how the
  1359.     // nodes were linked before doing the special-checking for
  1360.     // swapping adjacent nodes.
  1361.     //
  1362.     if(thisParent.Exists())
  1363.         thisLinkage = thisParent->IdentifyChild(t, this);
  1364.     if(othersParent.Exists())
  1365.         othersLinkage = othersParent->IdentifyChild(t, swapWith);
  1366.     
  1367.     //
  1368.     // Next, we need to do special-checking for adjacent records
  1369.     // (gasp, hack)
  1370.     //
  1371.     if(thisLeftSibling.Exists() && (thisLeftSibling->RecordIndex() == swapWith->RecordIndex()))
  1372.     {
  1373.         Require(othersParent->RecordIndex() == this->RecordIndex());
  1374.         thisLeftSibling = this;
  1375.         othersParent = swapWith;
  1376.     }
  1377.     if(thisRightSibling.Exists() && (thisRightSibling->RecordIndex() == swapWith->RecordIndex()))
  1378.     {
  1379.         Require(othersParent->RecordIndex() == this->RecordIndex());
  1380.         thisRightSibling = this;
  1381.         othersParent = swapWith;
  1382.     }
  1383.     if(othersLeftSibling.Exists() && (othersLeftSibling->RecordIndex() == this->RecordIndex()))
  1384.     {
  1385.         Require(thisParent->RecordIndex() == swapWith->RecordIndex());
  1386.         othersLeftSibling = swapWith;
  1387.         thisParent = this;
  1388.     }
  1389.     if(othersRightSibling.Exists() && (othersRightSibling->RecordIndex() == this->RecordIndex()))
  1390.     {
  1391.         Require(thisParent->RecordIndex() == swapWith->RecordIndex());
  1392.         othersRightSibling = swapWith;
  1393.         thisParent = this;
  1394.     }
  1395.     
  1396.     Try
  1397.     {
  1398.         //
  1399.         // Relink other node
  1400.         //
  1401.         swapWith->SetLeftSibling(t, thisLeftSibling);
  1402.         swapWith->SetRightSibling(t, thisRightSibling);
  1403.         swapWith->SetBalanceFactor(t, thisBalanceFactor);
  1404.         if(thisParent.Exists())
  1405.         {
  1406.             (this->Transaction()->GetDBRecordUpdatePointer(thisParent))->SetChildLinkOfNewParent(t, swapWith, thisLinkage);
  1407.             thisParent = nil;
  1408.         }
  1409.         else
  1410.             swapWith->SetParentSibling(t, nil);
  1411.         if(thisLeftSibling.Exists())
  1412.         {
  1413.             (this->Transaction()->GetDBRecordUpdatePointer(thisLeftSibling))->SetParentSibling(t, swapWith);
  1414.             thisLeftSibling = nil;
  1415.         }
  1416.         if(thisRightSibling.Exists())
  1417.         {
  1418.             (this->Transaction()->GetDBRecordUpdatePointer(thisRightSibling))->SetParentSibling(t, swapWith);
  1419.             thisRightSibling = nil;
  1420.         }
  1421.         
  1422.         //
  1423.         // Relink this node
  1424.         //
  1425.         this->SetLeftSibling(t, othersLeftSibling);
  1426.         this->SetRightSibling(t, othersRightSibling);
  1427.         this->SetBalanceFactor(t, otherBalanceFactor);
  1428.         if(othersParent.Exists())
  1429.         {
  1430.             (this->Transaction()->GetDBRecordUpdatePointer(othersParent))->SetChildLinkOfNewParent(t, AConst<TDBRecord>(this), othersLinkage);
  1431.             othersParent = nil;
  1432.         }
  1433.         else
  1434.             this->SetParentSibling(t, nil);
  1435.         if(othersLeftSibling.Exists())
  1436.         {
  1437.             (this->Transaction()->GetDBRecordUpdatePointer(othersLeftSibling))->SetParentSibling(t, this);
  1438.         }
  1439.         if(othersRightSibling.Exists())
  1440.         {
  1441.             (this->Transaction()->GetDBRecordUpdatePointer(othersRightSibling))->SetParentSibling(t, this);
  1442.         }
  1443.     }
  1444.     Catch(err)
  1445.     {
  1446.         Throw(err);
  1447.     }
  1448. } // TDBRecord::SwapTreePositions
  1449.  
  1450. //================================================================================
  1451. // Class TAbstractRecordIterator
  1452. //================================================================================
  1453.  
  1454. //--------------------------------------------------------------------------------
  1455. // TAbstractRecordIterator::TAbstractRecordIterator
  1456. //--------------------------------------------------------------------------------
  1457. TAbstractRecordIterator::TAbstractRecordIterator(TTransaction* transaction, AConst<TDBRecord> cursor, Boolean direction /* = kIterateForward */)
  1458. {
  1459.     fCursor = cursor;
  1460.     fDirection = direction;
  1461.     fTransaction = transaction;
  1462.     this->Reset();
  1463. }
  1464.  
  1465. //--------------------------------------------------------------------------------
  1466. // TAbstractRecordIterator::Reset
  1467. //--------------------------------------------------------------------------------
  1468. void TAbstractRecordIterator::Reset(Boolean direction /* = kIterateForward */)
  1469. {
  1470.     fDirection = direction;
  1471.     fHaveRemovedCurrent = false;
  1472.     if(fCursor.Exists())
  1473.     {
  1474.         if(this->IterateForward())
  1475.             fCurrent = fCursor->FirstItemInTree(fTransaction);
  1476.         else
  1477.             fCurrent = fCursor->LastItemInTree(fTransaction);
  1478.     }
  1479.     else
  1480.         fCurrent = nil;
  1481. } // TAbstractRecordIterator::Reset
  1482.  
  1483. //--------------------------------------------------------------------------------
  1484. // TAbstractRecordIterator::~TAbstractRecordIterator
  1485. //--------------------------------------------------------------------------------
  1486. TAbstractRecordIterator::~TAbstractRecordIterator()
  1487. {
  1488.     if(fCurrent.Exists())
  1489.     {
  1490.         fCurrent = AConst<TDBRecord>(nil);
  1491.     }
  1492. } // TAbstractRecordIterator::~TAbstractRecordIterator
  1493.     
  1494. //--------------------------------------------------------------------------------
  1495. // TAbstractRecordIterator::Next
  1496. //--------------------------------------------------------------------------------
  1497. void TAbstractRecordIterator::Next()
  1498. {
  1499.     if(fCurrent.Exists() && (fHaveRemovedCurrent == false))
  1500.     {
  1501.         AConst<TDBRecord> next;
  1502.  
  1503.         if(this->IterateForward())
  1504.             next = fCurrent->NextItemInTree(fTransaction);
  1505.         else
  1506.             next = fCurrent->PreviousItemInTree(fTransaction);
  1507.         
  1508.         fCurrent = next;
  1509.     }
  1510.     
  1511.     fHaveRemovedCurrent = false;
  1512. } // TAbstractRecordIterator::Next
  1513.  
  1514. //--------------------------------------------------------------------------------
  1515. // TAbstractRecordIterator::RemoveCurrent
  1516. //--------------------------------------------------------------------------------
  1517. void TAbstractRecordIterator::RemoveCurrent()
  1518. {
  1519.     fHaveRemovedCurrent = false;
  1520.     AConst<TDBRecord> recordToRemove = fCurrent;
  1521.     if(recordToRemove.Exists())
  1522.     {
  1523.         this->Next();
  1524.         (fTransaction->GetDBRecordUpdatePointer(recordToRemove))->RemoveFromTree(fTransaction);
  1525.         fHaveRemovedCurrent = true;
  1526.     }
  1527. } // TAbstractRecordIterator::RemoveCurrent
  1528.